The present invention relates to apparatus for either on-line or off-line testing of an electrical circuit. More particularly, the invention relates to circuit testing apparatus employing a linear feedback shift register ("LFSR") for signature analysis.
This application includes corresponding and additional subject matter to that of application Ser. No. 571,256 filed Jan. 16, 1984 in the name of Michael Whelan and commonly assigned with the present application.
Methods and apparatus for testing electrical circuits by "signature analysis" are well known. Commercial devices such as the Hewlett Packard HP 5004A signature analyzer have been available for a number of years. Publications describing such devices and methods of testing include "Hexadecimal Signatures Identify Trouble Spots in Microprocessor Systems" by G. Gordon et al., Electronics Magazine, Mar. 3, 1977, pp. 89-96; "Die Signatur-Analyse" by K. Heine, Elektronik Magazine (1979), Volume 1, pp. 48-51; "Logic-state and Signature Analysis Combine for Fast, Easy Testing" by I. Spector, Electronics Magazine, June 8, 1978, pp. 140-145.
With the signature analysis method of testing, an electrical circuit having an input and an output is connected at its output to a linear feedback shift register (LFSR) and connected at its input to an automatic test pattern generator (ATG). The ATG applies test patterns sequentially to the input of the circuit under test (CUT) for a prescribed number of test cycles. The output signals produced during this test sequence cause the LFSR to pass through a succession of specific states so that, after completion of the test, the LFSR contains a prescribed, known "signature" (bit pattern) if the ATG, the CUT and the LFSR are working properly.
Upon the completion of the test, the bit pattern in the LFSR is compared to the known bit pattern of the correct signature (i.e., the signature of a properly-working CUT) to determine whether any of the elements of the test system (ATG, CUT and LFSR) is faulty.
During the test, the contents of the LFSR change from one "signature" to the next as the LFSR moves through its successive states. For a 16-bit LFSR, for example, there are 2.sup.16 different possible signatures. Normally, however, the LFSR passes through only a small percentage of this maximum number of signatures during a given test.
Even assuming that the ATG and the LFSR hardware itself is functioning properly, the signature analysis method of circuit testing has two basic problems:
(1) It is difficult, if not impossible, to determine when (during which test cycle) the error appeared in the CUT from the final LFSR signature at the completion of the test sequence (assuming that the final signature is incorrect).
(2) It is possible for the LFSR to land in the correct state at the conclusion of a test sequence, indicating the correct signature, even though the CUT is faulty and produces multiple errors.
To understand the latter problem, it is necessary to analyze the error detection capabilities of the LFSR using probabilistic mathematics. It will be assumed, throughout this analysis, that all output symbols produced by the CUT are equally likely and there is no correlation between them. It will be assumed also (1) that the LFSR is designed to produce a maximal length random number sequence if continually presented with null symbols; (2) that the LFSR cannot get into a particular state from two different states upon receipt of the same input symbol and, similarly, (3) that the LFSR can only make a transition from one specific state to another upon receipt of one specific symbol.
Consider a test system with an ATG, CUT and LFSR connected together, which passes through N test cycles. The CUT therefore produces a string of N output symbols during the testing procedure which could be a correct sequence a or, in the alternative, an i symbol error sequence, b. b is thus a sequence of N symbols which differs from the sequence a in exactly i positions. It is assumed, in this regard, that all i symbol errors (for any particular value of i) are equally likely.
During the test sequence the LFSR starts in some initial state, S.sub.0, and compresses the string a or b of N symbols. In compressing these symbols, the LFSR will pass through N+1 states in total (including the initial and final states). However, since it is possible that states may be revisited, the number of distinct states may be less than this. We let A.sub.i denote the average number of distinct states visited when a string of i symbols is compressed; we let M denote the total number of LFSR states (e.g., 2.sup.16 for a 16-bit LFSR).
Now, therefore: EQU A.sub.0 =1 (i.e., the initial state) EQU A.sub.i+1 =A.sub.i +P,
where P is the probability that the (i+1).sup.st symbol causes a transition to a state which has not previously been visited. Since all symbols are equally likely, it follows that all next states are equally likely. ##EQU1##
This geometric series can be summed to yield: EQU A.sub.i =(1-.alpha..sup.i+1)/(1-.alpha.)
It follows that the fraction of states visited (on the average) during the compression of i symbols can be written as A.sub.i /M, a probability which we define as ".beta.."
FIG. 1 shows the results of this analysis for the case of an 8-bit LFSR as compared to actual observation. This graph sets forth the average number of different states visited by an LFSR (.beta.) in dependence upon the length of the LFSR sequence. For an 8-bit LFSR with 256 different states, there is a remote possibility that the LFSR will visit each state once during a 256 state sequence. However, as an average, the LFSR will visit only about 60 percent of these possible states during a 256 state sequence.
FIG. 1 thus shows the upper bound 2 for the number of different states which may be visited by the LFSR. The calculated average number of different states is indicated by the dash line 4, whereas actual observations are indicated by the solid lines 6 and 8. It can be seen that there is very good agreement between analysis and observation.
In considering the error coverage of the LFSR, it is necessary to define some additional notation:
a.sub.i =the i.sup.th symbol in a; andlikewise PA1 b.sub.i =the i.sup.th symbol in b; PA1 S.sub.i (a)=the LFSR state after processing the first i symbols of a; and PA1 S.sub.F (a)=the LFSR state after a has been completely compressed. PA1 P.sub.i =the probability that the LFSR detects an i-symbol error (i.e., an erroneous sequence yields an incorrect signature); and PA1 R.sub.i =the probability that the LFSR does not detect an i-symbol error (i.e., an erroneous sequence yields the correct signature). By definition P.sub.i =1-R.sub.i.
Furthermore,
We wish to determine P.sub.i and R.sub.i for i.gtoreq.1.